from collections import deque


# 图示例参考本目录下的: 示例.png图片
graph = {
    'A': ['C', 'E'],
    'B': ['F'],
    'C': ['B', 'D', 'F'],
    'D': ['F'],
    'E': ['F'],
    'F': [],  # 需要 防止KeyError
}

# 宽度优先搜索 - 先访问节点的第一层 后访问第二层 以此类推
def breadth_first_search(graph, v):
    """
    graph: 用邻接表表示
    v: 为起始顶点

    思路:
        a 入队
        队列不为空循环
            a出队
            标志为已经访问过
            这里可以打印输出访问结果
            遍历a的所有相邻节点w
                如果w还没有被访问过并且没在队列中(避免重复访问)
                    加入到队列中
    """
    # 使用双端队列 - pop和append都是O(1)复杂度
    queue = deque()
    queue.append(v)
    visited = set()
    while queue:
        v = queue.popleft()
        visited.add(v)
        print(v, end=" ")
        for w in graph[v]:
            if w not in visited and w not in queue:
                queue.append(w)
    

breadth_first_search(graph, 'A') # A C E B D F